package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - 使用最小花费爬楼梯
        Solution solution1 = new Solution();
        System.out.println("使用最小花费爬楼梯:");
        int[] cost1 = {10, 15, 20};
        System.out.println("cost = [10,15,20]: " + solution1.minCostClimbingStairs(cost1)); // 15
        int[] cost2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println("cost = [1,100,1,1,1,100,1,1,100,1]: " + solution1.minCostClimbingStairs(cost2)); // 6

        // 测试用例 - 解码方法
        Solution2 solution2 = new Solution2();
        System.out.println("\n解码方法:");
        System.out.println("s = \"12\": " + solution2.numDecodings("12")); // 2
        System.out.println("s = \"226\": " + solution2.numDecodings("226")); // 3
        System.out.println("s = \"06\": " + solution2.numDecodings("06")); // 0
    }

    // 使用最小花费爬楼梯
    static class Solution {
        int[] dp;

        public int minCostClimbingStairs(int[] cost) {
            int n = cost.length;
            dp = new int[n + 1];

            // 可以免费站在前两个台阶
            dp[0] = 0;
            dp[1] = 0;

            // 从位置2开始计算到楼梯顶部
            for (int i = 2; i <= n; i++) {
                // 从i-1跳1步 或 从i-2跳2步，取最小值
                dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
            }

            return dp[n];
        }
    }

    // 解码方法
    static class Solution2 {
        int[] dp;

        public int numDecodings(String s) {
            dp = new int[s.length()];
            char[] ch = s.toCharArray();

            // 首字符为0无法解码
            if (ch[0] == '0') return 0;
            dp[0] = 1;

            // 处理第二个字符
            if (ch.length > 1) {
                int twoDigits = (ch[0] - '0') * 10 + (ch[1] - '0');

                // 组合解码（10-26）
                if (twoDigits >= 10 && twoDigits <= 26) dp[1]++;

                // 单独解码（1-9）
                if (ch[1] != '0') dp[1]++;

                if (dp[1] == 0) return 0;
            }

            // 处理后续字符
            for (int i = 2; i < ch.length; i++) {
                int twoDigits = (ch[i - 1] - '0') * 10 + (ch[i] - '0');

                // 单独解码
                if (ch[i] - '0' >= 1 && ch[i] - '0' <= 9) {
                    dp[i] += dp[i - 1];
                }

                // 组合解码
                if (twoDigits >= 10 && twoDigits <= 26) {
                    dp[i] += dp[i - 2];
                }

                // 两种方式都不行
                if (dp[i] == 0) return 0;
            }

            return dp[ch.length - 1];
        }
    }
}